/**
 * @Author: lena
 * @Description:插入排序：将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。
 * @Version: 1.0.0
 * @Date: 2021/9/23 14:31
 */

package sort_array

// 插入规则：遍历有序序列，直到遇到第一个大于插入元素的元素，插入到该位置
func InsertionSort1(arr []int) {
    // 默认第一个元素是有序列表：[2, 4, 6, 8, 11, 12, 14, 7, 88, 4, 33, 11, 24, 18, 3]
    for i:=1 ; i<len(arr) ; i++ {
        data := arr[i]
        // 记录要插入的位置：若当前位置就是插入位置，则不会进入for中的if，因此初始值应该为当前位置
        insert := i
        // 寻找插入位置：从前往后找
        for j:=0;j<i;j++ {
            // 找到第一个大于当前元素的，将当前元素插入该位置
            if arr[j] > arr[i] {
                insert = j
                break
            }
        }
        // 将要插入位置后面的元素向后移
        out(arr,insert,i)
        // 将元素插入
        arr[insert]=data
    }
}

// 元素后移：将arr数组的(start,end]的元素向后移动一位
func out(arr []int,start int,end int) {
    for k:=end;k>start;k--{
        arr[k]=arr[k-1]
    }
}

// 插入规则：二分查找要插入的位置
func InsertionSort2(arr []int) {
    for i:=1;i< len(arr);i++ {
        data := arr[i]
        // 查找要插入的位置
        insert := quickIndex(arr,0,i-1,data)
        // 元素后移
        out(arr,insert,i)
        arr[insert]=data
    }
}

// 在arr数组的[start,end]中查找sign的插入位置返回
func quickIndex(arr[] int,start,end,sign int) int {
    i,j := start,end
    for i!=j {
        mid := (i+j)/2
        // 这样返回的序列是不稳定的
        if arr[mid] == sign {
            return mid
        }
        if arr[mid] > sign {
            j=mid-1
        } else {
            i=mid+1
        }
    }
    if arr[i] > sign {
        return i
    } else {
        return i+1
    }
}